Bregman-Minc inequality について

Words near each other

Dictionary Lists

mini英和辞書

翻訳と辞書　辞書検索 [ 開発暫定版 ]

スポンサードリンク

Bregman's Theorem ：ウィキペディア英語版

Bregman-Minc inequality
The Bregman-Minc inequality or Bregman's theorem is a theorem in discrete mathematics, which allows to estimate the permanent of a binary matrix via its row or column sums. The inequality was conjectured in 1963 by Henryk Minc and first proved in 1973 by Lev M. Bregman.〔〔 Further entropy-based proofs have been given by Alexander Schrijver and Jaikumar Radhakrishnan.〔〔 The Bregman-Minc inequality is used, for example, in graph theory to obtain upper bounds for the number of perfect matchings in a bipartite graph.
== Statement ==

The permanent of a square binary matrix

A = (a_)

of size

n

with row sums

r_i = a_ + \ldots + a_

for

i=1, \ldots , n

can be estimated by
:

\operatornameA \leq \prod_^n (r_i!)^.

The permanent is therefore bounded by the product of the geometric means of the numbers from

1

r_i

for

i=1, \ldots , n

. Equality holds if the matrix is a block diagonal matrix consisting of matrices of ones or results from row and/or column permutations of such a block diagonal matrix. Since the permanent is invariant under transposition, the inequality also holds for the column sums of the matrix accordingly.〔〔

抄文引用元・出典: フリー百科事典『ウィキペディア（Wikipedia）』
■ウィキペディアで「Bregman-Minc inequality」の詳細全文を読む

スポンサードリンク

翻訳と辞書 : 翻訳のためのインターネットリソース